package cn.hesion.dataStructures.singleLinkedList;

import java.util.Stack;

class LinkedList {
    //先初始化一个头节点, 头节点不要动, 不存放具体的数据
    private HeroNode head = new HeroNode(0, "");

    //返回头节点
    public HeroNode getHead() {
        return head;
    }

    public void add(HeroNode heroNode) {
        HeroNode temp = head;
        while (true) {

            if (temp.next == null) {
                // 这一步的目的是找到尾节点
                break;
            }
            //此时表明 还没找到尾节点。
            temp = temp.next;
        }
        // while循环结束表面已经找到尾节点了，开始执行插入，即给尾节点的next用新节点赋值
        temp.next = heroNode;
    }

    public void addOrderBy(HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false; //标志位表明待插入的节点的序号是否存在
//		while(true) {
//			if(temp != null) {
//				
//			}
//		
//		}
        // while循环结束表面已经找到尾节点了，开始执行插入，即给尾节点的next用新节点赋值
        temp.next = heroNode;
    }

    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
        }
        HeroNode temp = head.next;
        while (true) {
            if (temp.next == null) {
                // 这一步的目的是找到尾节点
                System.out.println(temp);
                break;
            }
            System.out.println(temp);
            temp = temp.next;


        }
    }

    /**
     * 用于获取倒数第index个节点
     * 思路：
     * 1.先把链表从头到尾遍历，求出链表长度，当然其实可以添加一个size属性，在添加的时候++，删除的时候--
     * 2.从头开始遍历，遍历到(size-index)个节点，就可以查到
     * 3.如果找到了就返回，如果没有找到就返回null
     *
     * @param head
     * @param index
     * @return
     */
    public HeroNode getLastIndexNode(HeroNode head, int index) {
        //先判断该链表是否为空
        if (head.next == null) {
            return null;
        }
        // 获取链表长度
        int size = getLength(head);
        // 倒数第k个就是正数第(size - index)个
        //校验index的值是否合法
        if (index < 0 || index > size) {
            return null;
        }
        // 定义个辅助变量
        HeroNode cur = head.next;
        // 开始从头遍历到第size-index个节点
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        //  找到该节点并返回
        return cur;

    }

    /**
     * 该函数用于求链表中有效节点的个数，
     * 1.遍历链表，length++
     *
     * @return
     */
    public int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }
        int length = 0;
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }

    // 将单链表进行反转
    public void reverseList(HeroNode head) {
        // 如果链表为空或者只有一个节点直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        // 辅助变量用于遍历节点
        HeroNode cur = head.next;
        //创建一个节点
        HeroNode reverseHead = new HeroNode(0, "");
        //指向当前节点的下一个节点
        HeroNode next = null;
        //开始遍历
        while (cur != null) {
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }

        head.next = reverseHead.next;
    }

    public void reversePrint(HeroNode head) {
        if (head.next == null) {
            return;
        }

        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }


    }
}